using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;


namespace SuchAlgorithmen
{
    public class RadixSort : SuchAlgorithmen.ISorter
    {
        private ArrayList _array;
        private List<Queue> _fifoListenspeicher;    
        private int _arrayGroesse;
        private int _anzahlZiffern;
        private int _bnaerigkeit;

        /// <summary>
        /// Konstruktor der Klasse RadixSort, es wird als Parameter eine Liste verlangt, die
        /// in der weiteren Anwendung benutzt wird
        /// </summary>
        /// <param name="array">Das zu sortierende Array</param>
        public RadixSort(ArrayList liste)
        {
            _bnaerigkeit = 10;                  //dezimalsystem
            _array = new ArrayList(liste);
            _arrayGroesse = _array.Count;
            _anzahlZiffern = _array[0].ToString().Length;
            _fifoListenspeicher = new List<Queue>(_bnaerigkeit);

            for (int i = 0; i < _fifoListenspeicher.Capacity; i++)
            {
                _fifoListenspeicher.Add(new Queue());
            }
        }
        

        private int[] AchieveDigits(int literal)
        {
            int[] digits = new int[_anzahlZiffern];
            int temp = literal;
                        
            for (int i = digits.Length-1, j = 0; i >=0 ; i--,j++)
            {
                digits[i] = (int)(temp / Math.Pow(_bnaerigkeit, _anzahlZiffern -1 - j));
                temp = temp % (int)Math.Pow(_bnaerigkeit, _anzahlZiffern - 1 - j);
            }

            return digits;
        }


        #region ISorter Member

        /// <summary>
        /// Sortiert die Liste
        /// </summary>
        /// <returns>void</returns>
        public void Sort()
        {
            for (int i = 0; i < _anzahlZiffern; i++)
            {
                for (int j = 0; j < _arrayGroesse; j++)
			    {
                    _fifoListenspeicher[AchieveDigits((int)_array[j])[i]].Enqueue(_array[j]);
			    }
                _array.Clear();
                for (int k = 0; k < _fifoListenspeicher.Capacity; k++)
                {
                    for (int l = 0; l < _fifoListenspeicher[k].Count; l=l)
                    {
                        _array.Add(_fifoListenspeicher[k].Dequeue());
                    }
                }
            }
        }

        /// <summary>
        /// Gibt den Wert in der Liste mit index i 
        /// </summary>
        /// <param name="index">Index i</param>
        /// <returns>int Den Wert in der Liste mit index i</returns>
        public int this[int i]
        {
            get { return (int) _array[i]; }
        }

        #endregion
    }
}
